package sort

object SortDemo {
    def main(args: Array[String]): Unit = {
        val arr1 = Array(40, 20, 30, -2, 100, 20)
        //quickSort(arr1,0,arr1.length-1)
        //println(arr1.mkString(","))

        mergeSort(arr1,0,arr1.length-1)
        println(arr1.mkString(","))

    }


    /**
      * 把数组拆碎完，碎成一个个的元素
      * @param arr
      * @param start
      * @param end
      */
    def mergeSort(arr: Array[Int], start: Int, end: Int): Unit = {
        if (start >= end) return
        val mid: Int = (start + end) / 2
        println(mid)
        mergeSort(arr, start, mid) // 把数组拆成两部分  左
        mergeSort(arr, mid + 1, end) // 右

        merge(arr, start, mid, end)
    }



    /**
      * 归并排序
      * @param arr
      * @param start
      * @param end
      */
    def merge(arr:Array[Int],start:Int,mid: Int,end:Int)={

        //增加哨兵
        val left = arr.slice(start,mid +1) :+ Int.MaxValue //:+ Int.MaxValue 加上最大的数就不会出现角标越界这种事
        val right = arr.slice(mid +1,end+1) :+ Int.MaxValue

        var m = 0 //left 的索引
        var n = 0//right 的索引

        for(i <- start to end){
            if (m > left.length -1){ //left.length -1  左边数组的下标
                arr(i) = right(n)
                n += 1
            }else if(n > right.length - 1 ){  //谁小放谁进数组
                arr(i) = left(m)
                m += 1

            }else if(left(m) <= right(n)){
                arr(i) = left(m)
                m += 1

            }else if(left(m) >right(n)){
                arr(i) = right(n)
                n += 1

            }

        }

    }



    /**
      * 函数式排序，涨涨见识
      * @param list
      * @return
      */
    def quick(list: List[Int]): List[Int] = {
        list match {
            case Nil => Nil
            case ::(head, tail) =>
                quick(tail.filter(_ <= head)) ::: head :: quick(tail.filter(_ > head)) //head为中间元素
        }
    }



    /**
      * 快排
      * @param arr
      * @param left
      * @param right
      */
    def quickSort(arr:Array[Int],left:Int,right:Int):Unit={
        //
        if(left >= right) return  //left、right索引
        val mid: Int = quickPartition(arr,left,right)

        //对左数组排序
        quickSort(arr,left,mid - 1)
        //对右数组排序
        quickSort(arr,mid + 1,right)
    }

    /**
      * 分区再排序
      * @param arr
      * @param left
      * @param right
      * @return
      */
    def quickPartition(arr:Array[Int],left:Int,right:Int): Int ={
        var low = left
        var high = right

        val p: Int = arr(left)  //数组最左的元素

        while(low < right){
            //
            while(low <= right && arr(low) <= p){
                low +=1

            }

            //
            while(high >= left && arr(high) > p){
                high -= 1
            }

            //
            if(low <= high){
                swap(arr,low,high)
            }

        }
        //
        swap(arr,left,high)  //数组元素交换
        high

    }

    def swap(arr :Array[Int],a:Int,b :Int)={
        val tmp = arr(a)
        arr(a) = arr(b)
        arr(b) = tmp
    }


}
